



/* 
 * File:   RBHash.h
 * Author: notnarb
 *
 */

#ifndef RBHASH_H
#define	RBHASH_H

#include <iostream>

#define HASH_SIZE 43


struct rbnode;

extern bool g_debug;

// Node used by the hash table
struct hnode {

  // value of the node
  int value;
  // pointer to the corresponding rbnode (values should match)
  rbnode* rbP;
  // pointer to the following node in the separate chain
  hnode* next;
};


// Node used by the red black tree
struct rbnode {
  // value of the node
  int value;
  // pointer to the corresponding hnode (values should match)
  hnode* hP;
  // boolean determining whether or not a node is black (red if not black)
  bool isBlack;
  // pointer to the left child rbnode
  rbnode* lP;
  // pointer to the right child rbnode
  rbnode* rP;
  // pointer to the parent node
  rbnode* parent;
  
  //@@@ DO NOT USE THIS, THIS DOESNT CHANGE AFTER ORIGINAL INSERT
  int height;
};



// Main structure as outlined in the assignment

class RBHash {
public:
    RBHash();
    RBHash(const RBHash& orig);
    virtual ~RBHash();


    void bulkLoad();
    void insert(int);
    void remove(int);
    void lookup(int);
    void range(int, int);
    void successor(int);
    void predecessor(int);
    void height();
    void children(int);
    void preorder(int);
    void printHT();

private:
    
    int insertCounter;
    void recurInsert(rbnode*, int, rbnode*);
    hnode* hashInsert(int, rbnode*);
    


    hnode* find(int);

    //pointer to the hash table
    hnode *hashTable[HASH_SIZE];
    
    
    //pointer to the red black tree
    rbnode *rbRoot;
    //dummy node;
    rbnode *dummy;

};

#endif	/* RBHASH_H */

